package practice;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * ConsecutiveNumbersSum
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: https://leetcode.cn/problems/consecutive-numbers-sum/ 829 连续整数求和
 * @date 2023/2/27
 **/
public class ConsecutiveNumbersSum {

    public static void main(String[] args) {
        Solution solution = new Solution();
        Solution1 solution1 = new Solution1();
        Solution2 solution2 = new Solution2();
        // 正确结果 4
//        System.out.println(solution.consecutiveNumbersSum(63660706));
//        System.out.println(solution.consecutiveNumbersSum(63660706));
//        System.out.println(solution1.consecutiveNumbersSum(63660706));
        // 正确结果 8
//        System.out.println(solution1.consecutiveNumbersSum(34624713));
        System.out.println(solution1.consecutiveNumbersSum(53965645));
        System.out.println(solution2.consecutiveNumbersSum(53965645));
    }

    private static class Solution1 {
        public int consecutiveNumbersSum(int n) {
            long start = System.currentTimeMillis();
            int cnt = 1;
            for (int i = 1; i < n; i++) {
                if (i + i + 1 > n) {
                    break;
                }
                int a = 1 - 2 * i;
                double c = Math.pow(2 * i - 1, 2) + 8 * n;
                double d = Math.sqrt(c);
                double x1 = (d + a) / 2;
                if (x1 > 0 && isInteger(x1)) {
                    cnt++;
                    continue;
                }
                double x2 = (-d + a) / 2;
                if (x2 > 0 && isInteger(x2)) {
                    cnt++;
                }
            }
            System.out.println("Solution1 use time = " + (System.currentTimeMillis() - start) + "ms");
            return cnt;
        }

        public boolean isInteger(double val) {
            return Math.round(val) == val;
        }
    }

    private static class Solution2 {
        public int consecutiveNumbersSum(int n) {
            long start = System.currentTimeMillis();

            int ans = 0;
            int bound = 2 * n;
            for (int k = 1; k * (k + 1) <= bound; k++) {
                if (isKConsecutive(n, k)) {
                    ans++;
                }
            }
            System.out.println("Solution2 use time = " + (System.currentTimeMillis() - start) + "ms");
            return ans;
        }

        public boolean isKConsecutive(int n, int k) {
            if (k % 2 == 1) {
                return n % k == 0;
            } else {
                return n % k != 0 && 2 * n % k == 0;
            }
        }
    }

    private static class Solution {
        public int consecutiveNumbersSum(int n) {
            if (n == 1) {
                return 1;
            }
            // 每个数至少有一个本身等于自己
            int cnt = 1;
            int lastSum = -1, lastVisitMaxIndex = -1;
            for (int i = 1; i < n; i++) {
                // 当前 + 下一个 已经大于 n 继续往后遍历没有意义
                if (i + i + 1 > n) {
                    break;
                }
                int j, sum = i;
                if (lastSum == -1) {
                    // 会不会越界？
                    j = i + 1;
                    while (sum < n && j < n) {
                        sum += j;
                        j++;
                        if (sum >= n) {
                            break;
                        }
                    }
                } else {
                    // lastSum == n 或者 lastSum > n 或者 lastSum < 0
                    j = lastVisitMaxIndex;
                    // j 有没有 可能等于i呢？
                    sum = lastSum - (i - 1);

                    if (sum > n) {
                        while (j > i) {
                            sum -= j;
                            if (sum <= n) {
                                break;
                            }
                            j--;
                        }

                    } else if (sum < n) {
                        while (j < n && j >= i) {
                            if (j == i) {
                                j++;
                                continue;
                            }
                            sum += j;
                            if (sum >= n) {
                                break;
                            }
                            j++;
                        }
                    }
                }

                if (sum == n) {
                    System.out.println("n = " + n + "; i = " + i + "; j = " + j);
                    cnt++;
                }

                lastSum = sum;
                lastVisitMaxIndex = j;
            }
            return cnt;
        }
    }
}
